package com.martain.leetcode.t124;

import com.martain.leetcode.common.TreeNode;

public class MaxPathSum {

    int result = Integer.MIN_VALUE;

    public  int getMaxSum(TreeNode node){
        if (node == null) return 0;
        dfs(node);
        return result;
    }

    public int dfs(TreeNode node)
    {
        if (node ==null) return 0;
        int left = Math.max(0,dfs(node.left));
        int right = Math.max(0,dfs(node.right));
        result = Math.max(result,(left+right+node.val));
        return (Math.max(left,right)+node.val);
    }

    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(1);
        treeNode.left = new TreeNode(2);
        treeNode.right = new TreeNode(3);
        MaxPathSum maxPathSum = new MaxPathSum();
        System.out.println(maxPathSum.getMaxSum(treeNode));
    }
}
